/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item12;

import org.junit.Assert;
import org.junit.Test;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:HasPath.java v1.0 2018/7/14 下午8:33 LvJing Exp $
 */
public class HasPath {

    private Solution solution;

    /**
     * 特殊输入
     */
    @Test
    public void test01() {
        solution = new Solution(null, 0, 0);
        Assert.assertFalse(solution.hasPath(null));
    }

    /**
     * 边界测试，矩阵只有一行
     */
    @Test
    public void test02() {
        solution = new Solution(new char[] { 'a', 'b', 't', 'g' }, 1, 4);
        Assert.assertTrue(solution.hasPath(new char[] { 'b', 't' }));
    }

    /**
     * 边界测试，矩阵只有一列
     */
    @Test
    public void test03() {
        solution = new Solution(new char[] { 'a', 'c', 'j' }, 3, 1);
        Assert.assertTrue(solution.hasPath(new char[] { 'a', 'c' }));
    }

    /**
     * 边界测试，矩阵和路径中所有字符相同
     */
    @Test
    public void test04() {
        solution = new Solution(new char[] { 'a', 'c', 'j' }, 3, 1);
        Assert.assertTrue(solution.hasPath(new char[] { 'a', 'c', 'j' }));
    }

    /**
     * 功能性测试，存在路径
     */
    @Test
    public void test05() {
        solution = new Solution(new char[] { 'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h' }, 3, 4);
        Assert.assertTrue(solution.hasPath(new char[] { 'b', 'f', 'c', 'e' }));
    }

    /**
     * 功能性测试，不存在路径
     */
    @Test
    public void test06() {
        solution = new Solution(new char[] { 'a', 'b', 't', 'g', 'c', 'f', 'c', 's', 'j', 'd', 'e', 'h' }, 3, 4);
        Assert.assertFalse(solution.hasPath(new char[] { 'a', 'b', 'f', 't' }));
    }
}

/**
 * 面试题12：判断矩阵中的路径，比如
 * a    b   t   g
 * c    f   c   s
 * j    d   e   h
 *
 * 查找该矩阵中是否包含bfce的路径，且路径不能重复进入格子。
 *
 * 思路：从头到尾遍历矩阵，找到任意一个等于指定字符串开头字符的坐标，以该坐标为基点，路径可以选择上下左右，各个方向依次进行判断是否等于字符串的
 * 第二个字符，不等就回退，让下一个方向进行判断，或者各个方向都不行，那就再回退，再遍历下一个基点，依次递归。同时要保证进入过的格子不能再次进入，
 * 使用一个布尔数组进行状态记录。
 */
class Solution {

    private char[] matrix;

    private int rows;

    private int cols;

    private boolean[] visitedFlag;

    Solution(char[] matrix, int rows, int cols) {
        this.matrix = matrix;
        this.rows = rows;
        this.cols = cols;
    }

    boolean hasPath(char[] str) {
        if (matrix == null || matrix.length == 0 || rows < 0 || cols < 0 || str == null || str.length == 0) {
            return false;
        }

        // 格子进入记录
        visitedFlag = new boolean[matrix.length];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPathCore(i, j, 0, str)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean hasPathCore(int row, int col, int strIndex, char[] str) {
        int index = cols * row + col;
        if (row < 0 || row >= rows || col < 0 || col >= cols || matrix[index] != str[strIndex] || visitedFlag[index]) {
            return false;
        }

        // 最后一个路径字符，不用再判断路径
        if (strIndex == str.length - 1) {
            return true;
        }

        visitedFlag[index] = true;
        if (hasPathCore(row - 1, col, strIndex + 1, str) || hasPathCore(row + 1, col, strIndex + 1, str) || hasPathCore(
                row, col - 1, strIndex + 1, str) || hasPathCore(row, col + 1, strIndex + 1, str)) {
            return true;
        }
        visitedFlag[index] = false;
        return false;
    }

}
